package com.liang.leetcode.array;

/**
 * 01：二分查找
 */
public class Array01_BinarySearch {
    public static void main(String[] args) {
        int[] nums = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
        // int index = binarySearch(nums, 15);
        int index = binarySearchTest(nums, 15);
        System.out.println(index);
    }

    /**
     * 二分查找
     * 情况一：左闭右闭，[left,right]
     * 根据区间的定义来判断循环条件和 left right 的赋值
     * @param nums
     * @param target
     * @return
     */
    private static int binarySearch(int[] nums, int target) {
        //先排除非法情况
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1; //需要包含右区间的值
        while (left <= right) {  //思考点1：是 < 还是 <=，因为[1,1]是合法区间，所以是 <=
            int mid = left + ((right - left) >> 1); //优化计算中间索引，避免溢出
            //先得到数组一半，再加上左边界就得到中间位置，left + right/2 - left/2 = right/2 - left/2 = (right - left) / 2
            //int mid = (left + right) / 2;
            //大左小右
            if (target > nums[mid]) { //target在右区间，更新左边界，[mid + 1, right]
                left = mid + 1;
            } else if (target < nums[mid]) { //target在左区间，更新右边界，[left, mid - 1]
                right = mid - 1;
            } else {  // nums[mid] == target
                return mid; //找到目标值，返回下标
            }
        }
        //未找到目标值
        return -1;
    }

    /**
     * 情况二：左闭右开，[left,right)
     * @param nums
     * @param target
     * @return
     */
    private static int binarySearch2(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // 不同点1：定义target在左闭右开的区间里，即：[left, right)
        while (left < right) {  // 不同点2：因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int mid = (left + right) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid; //不同点3：target 在左区间，在[left, middle)中
            } else {
                return mid;
            }
        }
        return -1;
    }

    private static int binarySearchTest(int[] nums, int target) {
        //确定左右边界
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target > nums[mid]) {
                //目标值比中间值大，说明在右边，更新左边界
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                //相等
                return mid;
            }
        }
        return -1;
    }
}
